package Greddy;

import java.util.Arrays;

/**
 * 435.无重叠区间
 * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 * 注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
 *
 */
public class eraseOverlapIntervals {
    /**
     * 一刷
     * 按照结束时间排序
     */
    public int eraseOverlapIntervals(int[][] intervals) {

        if (intervals.length == 0 || intervals.length == 1) return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));//按照结束时间进行排序，每次选择结束时间最早的区间，使得后续区间有更大的选择空间。
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= end) end = intervals[i][1];
            else {
                count++;
            }
        }
        return count;
    }
    /**
     * 二刷
     * 按照开始时间排序，这个更容易理解
     */
    public int eraseOverlapIntervals2(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int end = intervals[0][1];
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
            } else {
                count++;
                end = Math.min(intervals[i][1],end);
            }
        }
        return count;
    }
}
